package com.yequan.leetcode.tree.rightSideView_199;

import com.yequan.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 199. 二叉树的右视图
 *
 * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3,null,5,null,4]
 * 输出: [1, 3, 4]
 * 解释:
 * <p>
 * 1            <---
 * /   \
 * 2     3         <---
 * \     \
 * 5     4       <---
 *
 * @author yq
 * @date 2020/04/22
 */
public class RightSideView {

    /**
     * 深度优先遍历变种
     * 先获取根节点的值
     * 然后按照先访问右子树，再访问左子树
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (null == root) {
            return ans;
        }
        ans.add(root.val);
        helper(0, root, ans);
        return ans;
    }

    private void helper(int level, TreeNode node, List<Integer> ans) {
        if (null != node) {
            if (ans.size() == level) {
                ans.add(node.val);
            }
            helper(level + 1, node.right, ans);
            helper(level + 1, node.left, ans);
        }
    }

}
